package other;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Map;
import java.util.HashMap;

class City {
    int x, y;
    boolean visited;

    City(int x, int y) {
        this.x = x;
        this.y = y;
        this.visited = false;
    }
}

public class TravellingSalesman {

    // 计算距离函数
    static double calculateDistance(City city1, City city2) {
        return Math.sqrt(Math.pow(city1.x - city2.x, 2) + Math.pow(city1.y - city2.y, 2));
    }

    // 查找最近未访问城市函数
    static int findNearestCity(List<City> cities, Set<Integer> visited, int currentIndex) {
        double minDistance = Double.MAX_VALUE;
        int nearestCityIndex = -1;

        for (int i = 0; i < cities.size(); i++) {
            if (!visited.contains(i) && i != currentIndex) {
                double distance = calculateDistance(cities.get(currentIndex), cities.get(i));
                if (distance < minDistance) {
                    minDistance = distance;
                    nearestCityIndex = i;
                }
            }
        }

        return nearestCityIndex;
    }

    // 获取城市名称函数（使用Map来模拟switch-case）
    static String getCityName(int index) {
        Map<Integer, String> cityNames = new HashMap<>();
        cityNames.put(0, "广州");
        cityNames.put(1, "河内");
        cityNames.put(2, "曼谷");
        cityNames.put(3, "金边");
        cityNames.put(4, "吉隆坡");
        cityNames.put(5, "新加坡");
        cityNames.put(6, "文莱");
        cityNames.put(7, "马尼拉");
        return cityNames.getOrDefault(index, "未知城市"); // 理论上不会到达这里
    }

    public static void main(String[] args) {
        // 定义城市坐标
        List<City> cities = new ArrayList<>();
        cities.add(new City(525, 78));   // 广州
        cities.add(new City(327, 119));  // 河内
        cities.add(new City(232, 266));  // 曼谷
        cities.add(new City(314, 311));  // 金边
        cities.add(new City(255, 477));  // 吉隆坡
        cities.add(new City(296, 513));  // 新加坡
        cities.add(new City(510, 438));  // 文莱
        cities.add(new City(628, 246));  // 马尼拉

        // 存储访问顺序和已访问城市
        List<Integer> order = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();

        // 从广州出发
        int currentIndex = 0;
        order.add(currentIndex);
        visited.add(currentIndex);
        cities.get(currentIndex).visited = true;

        // 遍历城市
        for (int i = 0; i < cities.size() - 1; i++) { // 减去1，因为我们不访问最后一个城市后再去一个城市（直接返回广州）
            int nextCityIndex = findNearestCity(cities, visited, currentIndex);
            order.add(nextCityIndex);
            visited.add(nextCityIndex);
            cities.get(nextCityIndex).visited = true;
            currentIndex = nextCityIndex;
        }

        // 构建访问顺序字符串
        StringBuilder orderString = new StringBuilder();
        for (int index : order) {
            orderString.append(getCityName(index)).append(" -> ");
        }
        // 移除最后一个" -> "并添加返回广州
        if (!order.isEmpty()) {
            orderString.setLength(orderString.length() - 4); // 移除最后的" -> "
            orderString.append(" -> 广州");
        }

        // 输出访问顺序
        System.out.println("访问顺序: " + orderString.toString());
    }
}
